package minmax;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

/**
 * is implementation of min-max search algorithm.
 * 
 * @author alex
 */
public class MinMax {

    /**
     * current tree traversal depth
     */
    private int depth;
    /**
     * general limit for a search depth
     */
    private int depthBound;
    private final Random random;

    /**
     * create an instance
     * 
     * @param depthBound is >= 1
     */
    public MinMax(int depthBound) {
        if (depthBound < 1) {
            throw new IllegalArgumentException("depth bound must be >= 1: " + depthBound);
        }
        this.depthBound = depthBound;
        
        this.random = new Random();
    }

    /**
     * finds an optimal move for a current player
     * 
     * @param state is a game state, game must still be playable
     * @return optimal move
     */
    public <M extends GameMove> M minmax(GameState<M> state) {
        List<M> list = minmaxList(state);
        return list.get(random.nextInt(list.size()));
    }

    public <M extends GameMove> List<M> minmaxList(GameState<M> state) {
        if (state.isFinished()) {
            throw new IllegalArgumentException("The game has been finished, no further moves possible");
        }
        this.depth = 0;
        List<M> best = new ArrayList<M>();
        int alpha = Integer.MIN_VALUE, beta = Integer.MAX_VALUE;
        // go through children
        Iterator<M> moves = state.moves();
        assert moves.hasNext();
        while (moves.hasNext()) {
            M step = moves.next();
            int cursor = minMove(state, step, alpha, beta);
            // narrow the effective bound
            if (alpha == cursor) {
                best.add(step);
            } else if (alpha < cursor) {
                alpha = cursor;
                best.clear();
                best.add(step);
            }
        }
        assert best != null;
        return best;
    }

    /**
     * in general number of steps we can make is limited, but
     * certain implementations can relax this assumption by
     * overriding this method.
     * 
     * @param state is current game state
     * @param isMax determine the type of node
     * @param depth is the current stack size
     * @return whether next move is possible
     */
    protected boolean acceptable(GameState<?> state, boolean isMax, int depth) {
        return depth < depthBound;
    }

    /**
     * applies a move and tries to achieve next possible moves
     * 
     * @param state is current game state
     * @param step is a move to apply
     * @param isMax determines type of node we are at
     * @return either <code>null</code> or an iterator over non-empty set of moves
     */
    private <M extends GameMove> Iterator<M> descend(GameState<M> state, M step, boolean isMax) {
        depth++;
        state.move(step);
        if (!acceptable(state, isMax, depth) || state.isFinished()) {
            return null;
        } else {
            return state.moves();
        }
    }

    /**
     * withdraws the last move
     * 
     * @param state is current game state
     */
    private void ascend(GameState<?> state) {
        depth--;
        state.backtrack();
    }

    /**
     * processes max node of min-max search tree
     * 
     * @param state is current game state
     * @param step is a move to apply
     * @param alpha is the lower bound
     * @param beta is the upper bound
     * @return updated lower bound
     */
    public <M extends GameMove> int maxMove(GameState<M> state, M step, int alpha, int beta) {
        int result = Integer.MIN_VALUE;
        // make a move and examine the resulting state
        Iterator<M> moves = descend(state, step, true);
        if (moves == null) {
            // in case if no children available for further navigation, we return the heuristic estimate
            result = state.evaluate(true);
        } else {
            assert moves.hasNext();
            // go through children
            int cursor = 0;
            while (moves.hasNext()) {
                cursor = minMove(state, moves.next(), alpha, beta);
                if (result < cursor) {
                    result = cursor;
                }
                // prune useless branches
                if (beta <= cursor) {
                    break;
                }
                // narrow the effective bound
                if (alpha < cursor) {
                    alpha = cursor;
                }
            }
        }
        // backtrack the move
        ascend(state);
        return result;
    }

    /**
     * processes min node of min-max search tree
     * 
     * @param state is current game state
     * @param step is a move to apply
     * @param alpha is the lower bound
     * @param beta is the upper bound
     * @return updated upper bound
     */
    public <M extends GameMove> int minMove(GameState<M> state, M step, int alpha, int beta) {
        int result = Integer.MAX_VALUE;
        // make a move and examine the resulting state
        Iterator<M> moves = descend(state, step, false);
        if (moves == null) {
            // in case if no children available for further navigation, we return the heuristic estimate
            result = state.evaluate(false);
        } else {
            assert moves.hasNext();
            // go through children
            int cursor = 0;
            while (moves.hasNext()) {
                cursor = maxMove(state, moves.next(), alpha, beta);
                if (result > cursor) {
                    result = cursor;
                }
                // prune useless branches
                if (alpha >= cursor) {
                    break;
                }
                // narrow the effective bound
                if (beta > cursor) {
                    beta = cursor;
                }
            }
        }
        // backtrack the move
        ascend(state);
        return result;
    }

    @Override
    public String toString() {
        return "depth = " + depth + ", depthBound = " + depthBound;
    }
}
